package com.arron.algorithm.sort;

import java.util.Arrays;

/**
 *  快排的常见的两种拆分方法，一种是单指针，一种是双指针
 */
public class QuickSort {


    public static void main(String[] args) {

        int[] array = {8,3,7,12,2,3};

//        quickSort(array,0,array.length-1);

        quicksort3(array,0,array.length-1);
        print(array);
    }
    public void quickSortV(int[] nums,int left,int right){

        if (left>=right){
            return;
        }

        int  numIndex = sort(nums,left,right);

        System.out.println("numIndex : "+ numIndex+"  每轮的交换结果: "+ Arrays.toString(nums));
        quickSortV(nums, left, numIndex - 1);
        quickSortV(nums, numIndex + 1, right);
    }

    private int sort(int[] nums, int left, int right) {

        //这里默认使用left作为初始指针
       // int root = left;
        int p1 = left+1;
        int p2 = right;
        while (p1 <=  p2){

            //在左边找到第一个大于 nums[root] 的元素
            while (p1 <= p2 && nums[p1] <= nums[left]){
                p1++;
            }

            //在右边区间找到第一个小于nums[root] 的元素
            while (p2 >= p1 && nums[p2] > nums[left]){
                p2--;
            }

            if (p1 > p2){
                swapNums(nums, left,p2);
                break;
            }

            if(p1 <p2){

                swapNums(nums,p1,p2);
            }

        }
        return p2;
    }

    private void swapNums(int[] nums, int p1, int p2) {

        int temp = nums[p1];
        nums[p1] = nums[p2];
        nums[p2] = temp;
    }


    public static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }




    public static void quickSort2(int start,int end,int array[]){

        //递归结束的条件
        if(start >= end){
            return;
        }

        int base = partion2(start,end,array);

        quickSort2(start,base-1,array);
        quickSort2(base+1,end,array);
    }

    private static int partion2(int start, int end, int[] array) {
        int baseNumber = array[start];
        int mark = start;
        for (int i = start+1; i <= end; i++) {
            if (array[i] < baseNumber){
                mark++;
                int temp = array[mark];
                array[mark] = array[i];
                array[i] = temp;
            }
        }
        //将baseNumber和mark交换
        array[start] = array[mark];
        array[mark] = baseNumber;
        return mark;
    }


    /**
     * 递归 双指针拆分法
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int[] quickSort(int[] array,int start,int end){

        if (array == null || array.length <2){
            return array;
        }
        int partion = partion(array, start, end);

        if (partion > start){
            quickSort(array,start,partion-1);
        }

        if (partion<end){
            quickSort(array,partion+1,end);
        }


        return array;

    }



    public static int partion(int[] array,int start,int end){

        if (start == end){
            //如果只有一个元素之后就不进行排序了
            return start;
        }

        //1,选取一个基准数
        int pivot = (int)(start+Math.random()*(end-start+1));

        //1.2设置分区指示器

        int zoneIndex= start-1;
        //2.基准数与最后一个元素交换
        swap(array,pivot,end);

        //3.遍历数组

        for (int i =start;i<=end;i++) {

            //1.如果比基准数大不用动，继续遍历

            //2.如果比基准数小，且比较当前数的下标和分区指示器的下标大小，当前遍历的下标比分区指示器的下标大，则交换
            if (array[i] <= array[end]){
                zoneIndex++;
                if (i>zoneIndex){
                    swap(array,i,zoneIndex);
                }
            }
        }

        return zoneIndex;
    }

    private static void swap(int[] array, int pivot, int end) {
        int temp = array[pivot];
        array[pivot] = array[end];
        array[end] = temp;
    }





    public static void quicksort3(int[] array,int start,int end){

        //递归结束的条件
        if (start < end) {

            int l = start;
            int x = array[start];
            int r = end;

            while (l < r) {

                while (l < r && array[r] > x) {
                    r--;
                }
                if (l < r) {
                    array[l++] = array[r];
                }

                while (l < r && array[l] < x) {
                    l++;
                }
                if (l < r) {
                    array[r--] = array[l];
                }


            }

            array[r] = x;

            quicksort3(array, start, r - 1);


            quicksort3(array, r + 1, end);
        }

    }



}
